# encoding=utf8
'''
Created on 25 Oct 2012

@author: JoséJoão
'''
import copy

class Grafo( object ):
	def __init__( self, mat_adj ):
		self._mat_adj = mat_adj

	def conv_para_dic( self, grafo = {} ):
		'''Função que converte uma matriz de adjacências em um grafo'''
		for i in range( len( self._mat_adj ) ):
			chave = i
			valor = []
			for j in range( len( self._mat_adj ) ):
				if self._mat_adj[i][j] != 0:
					valor.append( j )
			grafo[chave] = valor
		return grafo

	@property
	def e_arvore( self ):
		'''Retorna a propriedade e_arvore True ou False se é uma árvore ou não'''
		if not self.tem_vert_isol and not self.e_direcionado and not self.tem_ciclo and self.e_conexo:
			return True
		else:
			return False

	@property
	def e_conexo( self ):
		'''Retorna a propriedade e_conexo como True ou False se for conexo ou não'''
		graph = self.conv_para_dic()
		e_conexo = False
		visitados = []
		q = [0]
		path = []
		while q:
			v = q.pop( 0 )
			if v not in path:
				path = path + [v]
				q = graph[v] + q
				visitados.append( v )

			if len( visitados ) == len( self._mat_adj ):
				e_conexo = True
				break
			else:
				e_conexo = False
		return e_conexo

	@property
	def e_completo( self ):
		'''Retorna a propriedade e_completo True ou False no caso de o grafo ser completo ou não'''
		graph = self.conv_para_dic()
		vertices = graph.keys()
		acertos = 0
		for ver in vertices:
			if len( vertices ) - 1 == len( graph[ver] ):
				for i in graph[ver]:
					for a in vertices:
						if i == a:
							acertos = acertos + 1
		if acertos == ( len( vertices ) * ( len( vertices ) - 1 ) ):
			return True
		else:
			return False

	@property
	def e_direcionado( self ):
		'''Verifica se o grafo é direcionado e retorna True ou False na propriedade e_direcionado'''
		matriz_adj = copy.copy( self._mat_adj )
		matriz = [tuple( row ) for row in matriz_adj]
		resultado = matriz != zip( *matriz_adj )
		return resultado

	def encontrar_caminho( self, grafo, inicio, final, caminho = [] ):
		'''Verifica se existe um caminho entre um nó e outro'''
		caminho = caminho + [inicio]
		if inicio == final:
			return caminho
		if not grafo.has_key( inicio ):
			return None
		for noh in grafo[inicio]:
			if noh not in caminho:
				novo_caminho = self.encontrar_caminho( grafo, noh, final, caminho )
				if novo_caminho: return novo_caminho
		return None

	def encontrar_todos_caminhos( self, inicio, fim, caminho = [] ):
		'''Encontra todos os caminhos entre um nó e outro'''
		caminho = caminho + [inicio]
		graph = self.conv_para_dic()
		if inicio == fim:
			return [caminho]
		if not graph.has_key( inicio ):
			return []
		caminhos = []
		for noh in graph[inicio]:
			if noh not in caminho:
				caminhos.extend( self.encontrar_todos_caminhos( noh, fim, caminho ) )
		return caminhos

	# Graus de Entrada:
	@property
	def grau_de_entrada( self ):
		'''Retorna a propriedade grau_de_entrada que é uma lista com o grau de entrada de cada vértice'''
		mat_adj_grau_entrada = []
		for i in range( len( self._mat_adj ) ):
			grau_de_entrada = 0
			for j in range( len( self._mat_adj ) ):
				grau_de_entrada += self._mat_adj[j][i]
			mat_adj_grau_entrada.append( grau_de_entrada )
		return mat_adj_grau_entrada

	# Graus de Saída:
	@property
	def grau_de_saida( self ):
		'''Retorna a propriedade grau_de_saida que é uma lista com o grau de saída de cada vértice'''
		mat_adj_grau_saida = []
		for line in self._mat_adj:
			grau_de_saida = 0
			for i in range( len( self._mat_adj ) ):
				grau_de_saida += line[i]
			mat_adj_grau_saida.append( grau_de_saida )
		return mat_adj_grau_saida

	# Graus
	@property
	def graus( self ):
		'''Retorna a propriedade graus que contém uma lista com os graus de cada vértice'''
		if not self.e_direcionado:
			return self.grau_de_entrada
		else:
			return [self.grau_de_entrada[i] + self.grau_de_saida[i] for i in range( len( self._mat_adj ) )]

	def mostrar( self ):
		'''Mostra a matriz'''
		for col in self._mat_adj:
			print col

	@property
	def tem_ciclo( self ):
		'''Retorna propriedade tem_ciclo como True se houver ciclo ou False se não tiver'''
		grafo = self.conv_para_dic()
		valores = [item for sublist in grafo.values() for item in sublist]  # nós que são destino de outros nós
		for chave in grafo.keys():

			# Aqui se verifica se um vértice isolado tem um ciclo em si mesmo
			if ( len( grafo[chave] ) == 1 and grafo[chave][0] == chave ) or chave not in valores:
				return True

			for subnoh in grafo[chave]:
				if not chave == subnoh:
					caminhos = self.encontrar_todos_caminhos( chave, subnoh )  # procura todos os caminhos entre nó e subnó
					if len( caminhos ) > 1:  # Se houver mais de um caminho entre nó e subnó então existe um ciclo
						return True

		return False

	@property
	def tem_vert_isol( self ):
		'''Retorna propriedade tem_vert_isolado como True se houver vértice isolado ou False se não tiver'''
		grafo = self.conv_para_dic()
		valores = [item for sublist in grafo.values() for item in sublist]  # nós que são destino de outros nós

		# verifica cada nó e aos quais ele está conectado, considerando que um nṕ com ciclo em si mesmo
		# e não conectado aos outros nós, ainda assim é isolado
		for chave in grafo.keys():
			if ( len( grafo[chave] ) == 1 and grafo[chave][0] == chave or grafo[chave] == [] ) and chave not in valores:
				return True
			else:
				tem_vertices_isolados = False
		return tem_vertices_isolados
